package com.zjsru.leetcode75.level1;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Author: cookLee
 * @Date: 2023-11-30
 * 最大子序列的分数
 */
public class MaxScore {

    /**
     * 主
     * \
     * 输入：nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
     * 输出：12
     * 解释：
     * 四个可能的子序列分数为：
     * - 选择下标 0 ，1 和 2 ，得到分数 (1+3+3) * min(2,1,3) = 7 。
     * - 选择下标 0 ，1 和 3 ，得到分数 (1+3+2) * min(2,1,4) = 6 。
     * - 选择下标 0 ，2 和 3 ，得到分数 (1+3+2) * min(2,3,4) = 12 。
     * - 选择下标 1 ，2 和 3 ，得到分数 (3+3+2) * min(1,3,4) = 8 。
     * 所以最大分数为 12
     * \
     * 输入：nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
     * 输出：30
     * 解释：
     * 选择下标 2 最优：nums1[2] * nums2[2] = 3 * 10 = 30 是最大可能分数。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaxScore maxScore = new MaxScore();
        int[] nums1 = new int[]{1, 3, 3, 2};
        int[] nums2 = new int[]{2, 1, 3, 4};
        int k = 3;
        System.out.println(maxScore.maxScore(nums1, nums2, k));
    }

    /**
     * 最高分数
     *
     * @param nums1 nums1
     * @param nums2 nums2
     * @param k     k
     * @return long
     */
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int len = nums1.length;
        Integer[] idxs = new Integer[len];
        for (int i = 0; i < len; i++) {
            idxs[i] = i;
        }
        // 按照降序进行排序,按照 nums2 中的元素从大到小对 idxs 数组进行排序，使得 idxs 中的元素按照对应的 nums2 中的元素值降序排列
        // 比如,在nums2里的是[2,1,3,4](对应的下标是[0,1,2,3]),如果对nums2排序的话[4,3,2,1](对应的下标是[3,2,0,1]), 此时 idxs为[3,2,0,1]
        Arrays.sort(idxs, (i, j) -> nums2[j] - nums2[i]);

        long res = 0L;
        //最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //即题目要的数组nums1的和
        long sum1 = 0;
        for (int idx : idxs) {
            // nums1是被动的跟随nums2取值的
            int x = nums1[idx];
            int y = nums2[idx];

            while (minHeap.size() > k - 1) {
                // 这个是k个元素都够了以后,还要继续遍历的时候才会进入,比如前k是4 3 2的时候,最小的是2,那么向下移动一个位置,变成3 2 1的时候,该把nums1里的1移除
                sum1 -= minHeap.poll();
            }
            minHeap.offer(x);
            sum1 += x;
            //符合条件时，y刚好就是前K个元素里最小的,因为是倒序排列的
            if (minHeap.size() == k) {
                long cur = sum1 * y;
                res = Math.max(res, cur);
            }
        }
        return res;
    }
}
